{\rtf1\ansi\ansicpg1252\cocoartf1187\cocoasubrtf390
{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;}
\margl1440\margr1440\vieww16620\viewh12700\viewkind0
\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\pardirnatural

\f0\fs36 \cf0 Implementing a queue using single linked list as underlying stub\
\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\pardirnatural

\fs24 \cf0 \
typedef struct Node \{\
    Node *next;\
    int data;\
    Node(int d): data(d) \{next = NULL;\}\
\};\
\
class Queue (\
public:\
    Queue(): head(NULL), tail(NULL) \{\}\
    ~Queue(): \{\
        while (head) \{\
            Node *cur = head;\
            head = head->next; \
            delete cur;\
        \}\
        tail = NULL;\
    \}\
    void enque(int data);  // append a new item to the tail\
    bool deque(int &data):  // extract the first item from the head\
private:\
    Node *head; \
    Node *tail;\
\}\
\
void Queue::enque(int data) \{\
    if (!head) \{ // no element\
        tail = new Node(data);\
        head = tail;\
    \} else \{\
        tail->next = new Node(data);\
        tail = tail->next;\
    \}\
\}\
\
bool Queue::deque(int &data) \{\
    if (!head) return false;\
    Node *cur = head;\
    head = head->next;\
    data = cur->data;\
    delete cur;    // de-allocate node\
    return true;\
\}}